package org.zdw.data.structure.practice;

/**
 * 归并排序
 */
public class MerginPra {

    public void sort(int[] array){
        if(array.length > 0){
            sort(array,0,array.length - 1);
        }
    }

    private void sort(int[] data,int left,int right){
        if(left < right){
            int center = (right+left)/2; //计算中间位置值
            sort(data,left,center);
            sort(data,center+1,right);
            merge(data,left,center,right);
        }
    }

    /**
     * 归并操作
     * @param data
     * @param left
     * @param center
     * @param right
     */
    private void merge(int[] data, int left, int center, int right){
        int[] temp = new int[right - left + 1];
        int i = left;
        int j = center+1;
        int k = 0;
        //归并排序是重最小单位进行归并操作，所以默认是有序的，两个队列合并，先从两个队列的头元素开始比较，小的先赋值给
        //辅助数组，然后继续比较下一个数值
        while (i <= center && j <= right){
            if(data[i] < data[j]){
                temp[k++] = data[i++];
            }else {
                temp[k++] = data[j++];
            }
        }

        //当左侧待合并数组有剩余的数据未赋值给辅助数组时执行
        while (i <= center){
            temp[k++] = data[i++];
        }

        //当右侧待合并数组有剩余的数据未赋值给辅助数组时执行
        while (j <= right){
            temp[k++] = data[j++];
        }

        //将辅助数组元素赋值给相应的原素组
        for (int x=0;x<temp.length;x++){
            data[x+left] = temp[x];
        }

    }
}
